//
// Created by wenyaxi on 24-10-30.
//
#include <common.h>

class Solution {
public:
    int lengthOfLIS(vector<int> &nums) {
        vector<int> dp(nums.size(), 0);
        dp[0] = 1;
        int maxLen = 1;
        for (int i = 1; i < nums.size(); i++) {
            int max_pre=0;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    max_pre = max(max_pre, dp[j]);
                }
            }
            dp[i]=max_pre+1;
            maxLen = max(maxLen, dp[i]);
        }
        return maxLen;
    }
};

int main(int argc, char *argv[]) {
    //[10,9,2,5,3,7,101,18]
    //[0,1,0,3,2,3]
    //[7, 7, 7, 7, 7, 7, 7]
    //1,3,6,7,9,4,10,5,6
    Solution s;
    vector<int> nums = {1,3,6,7,9,4,10,5,6};
    int length_of_lis = s.lengthOfLIS(nums);
    cout << length_of_lis << endl;
    return 0;
}
